#include "cx_timer.h"
extern cx_timer_interface_t cx_timer0;
#ifdef USE_DYNAMIC_MALLOC
cx_slist_t *cx_slist_create(void)
{
    cx_slist_t *list = cx_malloc(sizeof(cx_slist_t));
    list->head = CX_NULL;
    list->tail = CX_NULL;
    return list;
}
cx_slist_item_t *cx_slist_item_create(void)
{
    cx_slist_item_t *item = cx_malloc(sizeof(cx_slist_item_t));
    item->content = CX_NULL;
    item->next = CX_NULL;
    return item;
}
#else
void cx_slist_init(cx_slist_t *plist)
{
    plist->head = CX_NULL;
    plist->tail = CX_NULL;
}
void cx_slist_item_init(cx_slist_item_t *psitem, cx_pointer_t pconponent)
{
    psitem->next = CX_NULL;
    psitem->content = pconponent;
}
#endif
cx_slist_item_t *cx_slist_append(cx_slist_t *list, cx_slist_item_t *item)
{
    cx_slist_item_t *ret;
    item->next = CX_NULL;
    if(list->head == CX_NULL)
    {
        list->head = item;
        list->tail = item;
    }
    else
    {
        if(list->head == list->tail)
        {
            list->head->next = item;
        }
        list->tail->next = item;
        list->tail = item;
    }
		ret = list->tail;
    return ret;
}
cx_slist_item_t *cx_slist_preappend(cx_slist_t *list, cx_slist_item_t* item)
{
//   cx_slist_item_t *ret;
    if(list->head == CX_NULL)
    {
        list->head = item;
        list->tail = item;
//        ret = list->head;
    }
    else
    {
//        ret = list->head;
        item->next = list->head;
        list->head = item;
    }
    return list->head;
}

cx_slist_item_t* cx_slist_insert(cx_slist_item_t *pre, cx_slist_item_t* item)
{
    item->next = pre->next;
    pre->next = item;
    return pre;
}

cx_slist_item_t *cx_slist_seek(cx_slist_t * list, int num)
{
    cx_slist_item_t *ret;
    if(list->head == CX_NULL)
    {
        ret = CX_NULL;
    }
    else
    {
        ret = list->head;
        while(ret != CX_NULL && (num > 0))
        {
            ret = ret->next;
            --num;
        }
    }

    return ret;
}

#ifdef USE_DYNAMIC_MALLOC
cx_slist_item_t * cx_slist_free(cx_slist_t *list,cx_slist_item_t *item)
{
    cx_slist_item_t *ret = list->head,*tmp = CX_NULL;
    if(ret == item)
    {
        list->head = list->head->next;
        cx_free(ret);
    }
    else
    {
            while((ret != CX_NULL) && (ret->next != item))
        {
            ret = ret->next;
        }
        if(ret != CX_NULL)
        {
            tmp = ret->next;
            ret->next = ret->next->next;
            cx_free(tmp);
            ret = tmp;
        }
    }
    return ret;
}

cx_slist_item_t * cx_slist_item_free_all(cx_slist_t *list)
{
    cx_slist_item_t *ptr = list->head;
    cx_slist_item_t *next = list->head->next;
    while(ptr != CX_NULL)
    {
        next = ptr->next;
        cx_free(ptr);
        ptr = next;
    }
    list->head = CX_NULL;
    list->tail = CX_NULL;
    return CX_NULL;
}
#else
cx_slist_item_t * cx_slist_item_delete(cx_slist_t *list, cx_slist_item_t *item)
{
    cx_slist_item_t *ret = list->head;
    if(ret == item)
    {
        list->head = list->head->next;
        if(list->tail == item)
        {
            list->tail = CX_NULL;
        }
    }
    else
    {
        while((ret != CX_NULL) && (ret->next != item))
        {
            ret = ret->next;
        }
        if(ret != CX_NULL)
        {
            if(list->tail == ret->next)
            {
                list->tail = ret;
            }
            ret->next = ret->next->next;
            ret = item;
        }
        else
        {
            ret = CX_NULL;
        }
    }
    return ret;
}
#endif

/*****************Sort functions*****************/
cx_slist_item_t* cx_slist_shortSortInList(cx_slist_item_t* head, 
                                cx_bool_t (*item_compare)(cx_slist_item_t*front,cx_slist_item_t*behind)) {
    cx_slist_item_t VirtualHead, *pVHead, *cur, *temp;
    VirtualHead.next = head;
    pVHead = &VirtualHead;
    while (pVHead->next != CX_NULL) {
        cur = pVHead->next;
        while (cur->next != CX_NULL) {
            if (/*cur->next->val < pVHead->next->val:cur->next will be take to the front*/item_compare(cur->next,pVHead->next) == cx_true) {
                temp = cur->next->next;
                cur->next->next = pVHead->next;
                pVHead->next = cur->next;
                cur->next = temp;
            } else {
                cur = cur->next;
            }
        }
        pVHead = pVHead->next;
    }
    return VirtualHead.next;
}

cx_slist_item_t* cx_slist_MergeSortedList(cx_slist_item_t*pHead1,cx_slist_item_t*pHead2,
                            cx_bool_t (*item_compare)(cx_slist_item_t*front,cx_slist_item_t*behind))
{
    cx_slist_item_t VirtualHead,*cur;
    VirtualHead.next = CX_NULL;
    cur = &VirtualHead;
    while((pHead1 != CX_NULL) || (pHead2 != CX_NULL))
    {
        if(pHead1 == CX_NULL)
        {
            cur->next = pHead2;
            pHead2=pHead2->next;
        }
        else if(pHead2 == CX_NULL)
        {
            cur->next = pHead1;
            pHead1=pHead1->next;
        }
        else {
            if(/*pHead1->val < pHead2->val: pHead1 will be take to the slist */item_compare(pHead1,pHead2) == cx_true)
            {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }
            else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
        }
        cur = cur->next;
    }
    return VirtualHead.next;
}

cx_slist_item_t* cx_slist_dichotomySortInList(cx_slist_item_t* head, cx_bool_t (*item_compare)(cx_slist_item_t*front,cx_slist_item_t*behind)) {
    // write code here
    cx_slist_item_t* slow,*fast;
    if(head == CX_NULL)
    {
        return CX_NULL;
    }
    slow = head;
    fast = head->next;
    while((fast->next != CX_NULL) && (fast != CX_NULL))
    {
        slow = slow->next;
        fast=fast->next->next;
    }
    fast = slow->next;
    slow->next = CX_NULL;
    slow = cx_slist_shortSortInList(head,item_compare);
    fast = cx_slist_shortSortInList(fast,item_compare);
    head = cx_slist_MergeSortedList(slow, fast,item_compare);
    return head;
}

cx_slist_item_t*cx_slist_reverseList(cx_slist_item_t*head ) {
    // write code here
    cx_slist_item_t VirtualHead,*temp;
    VirtualHead.next = CX_NULL;
    while(head!=CX_NULL)
    {
        temp = head->next;
        head->next = VirtualHead.next;
        VirtualHead.next = head;
        head = temp;
    }
    return VirtualHead.next;
}

cx_slist_item_t* cx_slist_reverseListBetween(cx_slist_item_t* head, int m, int n ) {
    // write code here
    int  i=1;
    cx_slist_item_t VirtualHead,*cur,*vHead,*temp,*pre;
    VirtualHead.next = head;
    cur = &VirtualHead;
    while((i!=m) && (cur->next != CX_NULL))
    {
        cur=cur->next;
        i++;
    }
    vHead = cur;
    cur = cur->next;
    pre = cur;
    cur=cur->next;
    while((i!=n) && (cur != CX_NULL))
    {
        temp = cur->next;
        cur->next = vHead->next;
        vHead->next = cur;
        cur = temp;
        i++;
    }
    pre->next = cur;
    return VirtualHead.next;
}

cx_slist_item_t* cx_slist_sort_first_to_end(cx_slist_t *slist)
{
    cx_slist_item_t *ret;
    if(slist->head != CX_NULL)
    {
        ret = slist->head;
        if(ret->next != CX_NULL)
        {
            slist->head = ret->next;
            cx_slist_append(slist,ret);
        }
    }
    else
    {
        ret = CX_NULL;
    }
    return  ret;
}

/*******************Sort functions end**************************/

/************************Check functions************************/
cx_bool_t cx_slist_hasCycle(cx_slist_item_t* head ) {
    // write code here
    cx_slist_item_t*slow=head,*fast=head;
    if(head == CX_NULL)
    {
        return cx_false;
    }
    fast = fast->next;
    while((fast != CX_NULL) && (fast->next != CX_NULL))
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
        {
            return cx_true;
        }
    }
    return cx_false;
}

/************************Check functions end************************/